import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 912. 排序数组
 * https://leetcode-cn.com/problems/sort-an-array/
 */
public class Solutions_912 {
    public static void main(String[] args) {
        int[] nums1 = {5, 2, 3, 1};  // output: {1, 2, 3, 5}
        int[] nums2 = {5, 1, 1, 2, 0, 0};  // output: {0, 0, 1, 1, 2, 5}
        int[] nums3 = {2, 6, 12, 10, 11, 16, 4, 7};
        // output: {2, 4, 6, 7, 10, 11, 12, 16}
        int[] nums4 = {-1, 2, -8, -10};
        // output: {-10, -8, -1, 2}
        int[] nums5 = {6, 2};  // output: {2, 6}
        int[] nums6 = {16, 11, 12};  // output: {11, 12, 16}

        List<int[]> inputs = new ArrayList<>();
        inputs.add(nums1);
        inputs.add(nums2);
        inputs.add(nums3);
        inputs.add(nums4);
        inputs.add(nums5);
        inputs.add(nums6);

        for (int[] input: inputs) {
            int[] result = sortArray(input);
            System.out.println(Arrays.toString(result));
        }
    }

    public static int[] sortArray(int[] nums) {
        // 解法一：冒泡排序（超时）
//        return BubbleSort.bubbleSort(nums);

        // 解法二：归并排序（7ms）
//        return MergeSort.mergeSort(nums);

        // 解法三：计数排序（2ms）
//        return CountingSort.countingSort(nums);

        // 解法四：选择排序（1171ms）
//        return SelectionSort.selectionSort(nums);

        // 解法五：插入排序（625ms）
//        return InsertSort.insertSort(nums);

        // 解法六：基数排序（350ms）
//        return RadixSort.radixSort(nums);

        // 解法七：桶排序（6ms）
//        return BucketSort.bucketSort(nums);

        // 解法八：希尔排序（9ms）
//        return ShellSort.shellSort(nums);

        // 解法九：堆排序（15ms）
//        return HeapSort.heapSort(nums);

        // 解法十：快速排序（5ms）
        return QuickSort.quickSort(nums);
    }
}
